package com.example.maze.generator;

import com.example.maze.model.Cell;
import com.example.maze.model.Coordinate;
import com.example.maze.model.Maze;
import com.example.maze.util.UnionFind;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.*;

/**
 * 使用Kruskal算法和并查集生成完美迷宫
 * 
 * 算法原理：
 * 1. 将所有可能的墙看作边，所有单元格看作节点
 * 2. 随机排列所有墙
 * 3. 对每堵墙，如果移除它能连接两个不同的区域，则移除
 * 4. 继续直到所有单元格都连通
 * 
 * @author maze-demo
 */
public class KruskalGenerator implements MazeGenerator {
    private static final Logger logger = LoggerFactory.getLogger(KruskalGenerator.class);
    
    private final Random random;
    
    /**
     * 表示两个相邻单元格之间的墙
     */
    private static class Wall {
        final Coordinate cell1;
        final Coordinate cell2;
        
        Wall(Coordinate cell1, Coordinate cell2) {
            this.cell1 = cell1;
            this.cell2 = cell2;
        }
        
        @Override
        public String toString() {
            return String.format("Wall[%s<->%s]", cell1, cell2);
        }
    }

    public KruskalGenerator() {
        this.random = new Random();
    }

    public KruskalGenerator(long seed) {
        this.random = new Random(seed);
    }

    @Override
    public void generate(Maze maze) {
        logger.info("开始使用Kruskal算法生成 {}x{} 迷宫", maze.getRows(), maze.getCols());
        
        long startTime = System.currentTimeMillis();
        
        // 1. 初始化：所有单元格都是墙，只有奇数坐标是潜在的通路
        initializeMaze(maze);
        
        // 2. 创建并查集，每个单元格初始为独立集合
        UnionFind<Coordinate> unionFind = new UnionFind<>();
        List<Coordinate> cells = initializeUnionFind(maze, unionFind);
        
        // 3. 创建所有可能的墙（相邻单元格之间）
        List<Wall> walls = createWalls(maze, cells);
        
        // 4. 随机打乱墙的顺序
        Collections.shuffle(walls, random);
        
        // 5. 使用Kruskal算法移除墙
        int removedWalls = removeWalls(maze, walls, unionFind);
        
        // 6. 设置起点和终点
        setStartAndEnd(maze, cells);
        
        long endTime = System.currentTimeMillis();
        logger.info("Kruskal算法生成完成，耗时: {}ms，移除墙数: {}", endTime - startTime, removedWalls);
    }

    /**
     * 初始化迷宫，所有单元格为墙，奇数坐标为潜在通路
     */
    private void initializeMaze(Maze maze) {
        // 创建棋盘格模式：只有奇数坐标(1,1), (1,3), (3,1), (3,3)等可能成为通路
        for (int row = 1; row < maze.getRows(); row += 2) {
            for (int col = 1; col < maze.getCols(); col += 2) {
                maze.setCell(row, col, Cell.Type.PATH);
            }
        }
    }

    /**
     * 初始化并查集，将所有通路单元格添加到并查集中
     */
    private List<Coordinate> initializeUnionFind(Maze maze, UnionFind<Coordinate> unionFind) {
        List<Coordinate> cells = new ArrayList<>();
        
        for (int row = 1; row < maze.getRows(); row += 2) {
            for (int col = 1; col < maze.getCols(); col += 2) {
                Coordinate coord = new Coordinate(row, col);
                unionFind.makeSet(coord);
                cells.add(coord);
            }
        }
        
        logger.debug("初始化了 {} 个单元格到并查集", cells.size());
        return cells;
    }

    /**
     * 创建所有可能的墙（相邻单元格之间）
     */
    private List<Wall> createWalls(Maze maze, List<Coordinate> cells) {
        List<Wall> walls = new ArrayList<>();
        
        for (Coordinate cell : cells) {
            int row = cell.getRow();
            int col = cell.getCol();
            
            // 检查右边的单元格
            if (col + 2 < maze.getCols()) {
                Coordinate rightCell = new Coordinate(row, col + 2);
                walls.add(new Wall(cell, rightCell));
            }
            
            // 检查下方的单元格
            if (row + 2 < maze.getRows()) {
                Coordinate downCell = new Coordinate(row + 2, col);
                walls.add(new Wall(cell, downCell));
            }
        }
        
        logger.debug("创建了 {} 堵墙", walls.size());
        return walls;
    }

    /**
     * 使用Kruskal算法移除墙
     */
    private int removeWalls(Maze maze, List<Wall> walls, UnionFind<Coordinate> unionFind) {
        int removedWalls = 0;
        
        for (Wall wall : walls) {
            // 如果两个单元格不在同一个连通分量中，移除它们之间的墙
            if (!unionFind.connected(wall.cell1, wall.cell2)) {
                // 合并两个连通分量
                unionFind.union(wall.cell1, wall.cell2);
                
                // 移除墙（将墙位置设置为通路）
                removeWallBetween(maze, wall.cell1, wall.cell2);
                removedWalls++;
            }
        }
        
        return removedWalls;
    }

    /**
     * 移除两个单元格之间的墙
     */
    private void removeWallBetween(Maze maze, Coordinate cell1, Coordinate cell2) {
        int wallRow = (cell1.getRow() + cell2.getRow()) / 2;
        int wallCol = (cell1.getCol() + cell2.getCol()) / 2;
        
        maze.setCell(wallRow, wallCol, Cell.Type.PATH);
    }

    /**
     * 设置起点和终点
     */
    private void setStartAndEnd(Maze maze, List<Coordinate> cells) {
        if (cells.isEmpty()) {
            throw new IllegalStateException("没有可用的单元格设置起点和终点");
        }
        
        // 随机选择起点和终点
        Collections.shuffle(cells, random);
        Coordinate start = cells.get(0);
        Coordinate end = cells.get(cells.size() - 1);
        
        // 确保起点和终点不同
        if (start.equals(end) && cells.size() > 1) {
            end = cells.get(1);
        }
        
        maze.setStart(start);
        maze.setEnd(end);
        
        logger.debug("设置起点: {}, 终点: {}", start, end);
    }

    @Override
    public String getName() {
        return "Kruskal";
    }
}